گروه نرم افزاری شاپرک

 

 

فرض کنید مجموعه ای از صفحات که حاوی پرس و جوی کاربر هستند را در اختیار دارید ، اکنون زمان آن رسیده است که بر اساس میزان انطباق با پرس و جو ، رتبه بندی را انجام دهیم. گوگل از فاکتورهای زیادی برای رتبه بندی نتایج پرس و جو استفاده می­کند. برای این منظور الگوریتم رتبه صفحه یکی از بهترین الگوریتم­هاست.

 

رتبه صفحه 2 چیز را ارزیابی می­کند :

 

1. به یک صفحه­ی وب چند لینک از صفحات دیگر وجود دارد.

 

2. کیفیت سایت­هایی که به آن­ها پیوند داده شده است.

 

در رتبه صفحه 5 تا 6 پیوند با کیفیت از سایت­هایی نظیر CNN و NyTimes بیش از 2 برابر تعداد زیادی پیوند از سایت­های کم ارزش تر ، ارزش دهی می­شود. البته گوگل از بسیاری فاکتورهای دیگر در کنار رتبه صفحه استفاده می­کند. مثلاً اگر سندی حاوی کلمات جنگ و سرد دقیقاً کنار یکدیگر باشد ، ممکن است مرتبط تر از سندی باشد که جنگ انقلابی را در مورد بحث قرار داده و بعضی جاها کلمه سرد را استفاده کرده است.

 

هم چنین اگر یک صفحه دارای کلمات جنگ سرد در عنوان خود باشد ، این خود سرنخی است که نشان می­دهد محتویات این صفحه مرتبط تر از صفحه ایست که عنوان آن مد آمریکا در قرن نوزدهم می­باشد. هم چنین اگر کلمات جنگ سرد چند بار در صفحه ای تکرار شوند ، این صفحه به نظر بهتر از صفحه ایست که این کلمات تنها یک بار در آن آمده اند.

 

به عنوان یک قانون ، گوگل سعی می­کند صفحاتی را پیدا کند که هم معتبرترند و هم مرتبط تر. اگر دو صفحه پیدا شوند که در یک پرس و جو مطالبشان تقریباً به یک اندازه با موضوع جست و جو انطباق دارد ، معمولاً صفحه ای انتخاب می­شود که سایت­های معتبرتر و مطمئن تری به آن پیوند دارد.

 

هم چنین برای یک صفحه با پیوندهای کم تر و رتبه­ی پایین تر ، در صورتی که نشانه­های دیگری ثابت کنند که صفحه مرتبط تر است را ممکن است در سطح بالایی رتبه بندی کند. مثلاً صفحه ای که کاملا به موضوع جنگ سرد اختصاص یافته مفیدتر از مقاله ایست که جنگ سرد را سرسری بررسی کرده است. حتی اگر مقاله بخشی از یک سایت معتبر و آبرومند مثل Time.com باشد. هنگامی که لیست اسناد و امتیازهای آن­ها ساخته شد اسناد با بالاترین امتیاز به عنوان سندی که بیشترین انطباق را دارند انتخاب می­شوند.

 

گوگل قدری کار اضافه هم انجام می­دهد تا خلاصه – چند کلمه که خلاصه ای از سند پیدا شده را نمایش می­دهد و عبارت پرس و جو در آن غلامت زده شده است – را نشان دهد. بیایید به پیوند­های رتبه بندی شده و خلاصه­هایی که به عنوان نتیجه به کاربر نشان داده می­شوند بر گردیم.

 

اجرای یک موتور جست و جو مقدار زیادی از منابع محاسباتی را به کار می­گیرد. برای هر پرس و جو که کاربر وارد می­کند ، بیش از 500 کامپیوتر ممکن است برای پیدا کردن بهترین اسناد ، کار کنند و همه اینها در کم تر از نیم ثانیه اتفاق می­افتد ]18[.

 

1-1- الگوریتم امتیاز صفحه­ی گوگل

 

امتیاز صفحه موضوعیست که بیشتر توسط متخصصان بهینه سازی موتورهای جست و جو  مورد بحث قرار می­گیرد. در قلب امتیاز صفحه فرمولهای ریاضی وجود دارد که در ظاهر ترسناک به نظر می­آیند ، اما فهم آن در حقیقت ساده است.

 

1-1-1- GoogleToolbar گوگل

 

گوگل دارای ابزاریست به نام GoogleToolbar که اگر آن را نصب کنید در نوار ابزار مرورگر شما ظاهر شده و هنگام گشت زنی در وب وارد هر سایتی که بشوید رتبه­ی آن را (با استفاده از الگوریتم امتیاز صفحه­ی گوگل ) به شما نشان می­دهد. این ابزار بسته به میزان رتبه­ی سایت ، عددی بین 1 تا 10 را نمایش می­دهد.

 

البته حداکثر امتیاز صفحه­ی صفحات هر ماه که گوگل اندیس گذاری مجدد انجام می­دهد ، تغییر می­کند. اگر فرض کنیم که مقیاس الگوریتمی­ باشد ، پس گوگل می­تواند به سادگی بالاترین مقیاس را در نوار ابزار همان 10 بدهد و بقیه را در شکل مناسبی مقیاس دهی کند ]8[.

 

1-1-2- بررسی امتیاز صفحه

 

در یک کلمه امتیاز صفحه یک رای است که میزان اهمیت یک صفحه را معین می­کند. پیوند دادن به یک صفحه در واقع رای پشتیبانی به آن صفحه می­باشد. اگر پیوندی وجود نداشته باشد ، پشتیبانی هم وجود ندارد.

 

بر اساس اسناد اصلی گوگل امتیاز صفحه بدین گونه تعریف می­شود :

 

فرض می­کنیم صفحه­ی A ، صفحات T₁... T_n را دارد که به آن اشاره می­کنند. پارامتر d یک فاکتور تعدیل است که عددی بین صفر و یک می­باشد. معمولاً d= 0.85 در نظر می­گیریم. هم چنین C(A) تعداد پیونهای خارج شده از صفحه­ی A می­باشد. امتیاز صفحه­ی صفحه­ی A به صورت زیر حساب می­شود:

 

PR(A) = (1-d) + d(PR(T₁)/C(T₁)+...+PR(T_n)/C(T_n))

 

ملاحظه می­کنید که امتیاز صفحه یک توزیع احتمال را روی صفحات وب شکل می­دهد ، بنابراین جمع امتیاز صفحه­ی همه­ی صفحات وب 1 است.

 

نکته : امتیاز صفحه یا PR(A) با استفاده از یک الگوریتم تکرارشونده­ی  ساده می­تواند باشد.

 

PR(T_i) : امتیاز صفحه­ی i امین صفحه.

 

C(T_i) : هر صفحه رای خود را به طور مساوی بین همه­ی پیوندهای خروجی اش تقسیم می­کند. تعداد پیونهای خروجی برای صفحه 1 ، C(T₁) ، برای صفحه n ، C(T_n) است و به همین ترتیب برای بقیه­ی صفحات.

 

PR(T_n)/C(T_n) : اگر از صفحه n به صفحه A پیوندی وجود دارد ، رایی که صفحه A می­گیرد برابر است با PR(T_n)/C(T_n).

 

d : یعنی فاکتور تعدیل. همه­ی این آرا با هم جمع می­شوند ولی برای جلوگیری از اینکه صفحات دیگر تاثیر بیش از اندازه ای داشته باشند ، حاصل جمع برای تبدیل شدن در 0.85 ضرب می­شود.

 

(1-d) : یعنی اگر هیچ پیوندی به یک صفحه وجود نداشته باشد (یعنی صفحه هیچ BackLink ی نداشته باشد ) در آن صورت باز هم یک امتیاز صفحه کوچک به اندازه 0.15 می­گیرد. در مستندات اصلی گوگل به عنوان جمع نرمال سازی مطرح شده است ]2[.

 

1-1-3- امتیاز صفحه چگونه محاسبه می­شود ؟

 

امتیاز صفحه­ی هر صفحه بستگی به امتیاز صفحاتی دارد که به آن صفحه اشاره می­کنند. اما تازمانی که امتیاز صفحه­ی صفحاتی را که به یک صفحه اشاره می­کنند را ندانیم ، نمی­توانیم امتیاز صفحه­ی آن صفحه را به دست آوریم و هنگامی که می­بینید پیوندهای آن صفحه حالت حلقه ایجاد می­کنند ، انجام این محاسبات غیرممکن است. اما در واقع به این بدی هم نیست. این قسمت از مستندات گوگل را به خاطر بسپارید :

 

امتیاز صفحه یا PR(A) با استفاده از الگوریتم تکرار شونده­ی ساده قابل انجام است.

 

آنچه برای ما معنی دارد این است که می­توانیم امتیاز صفحه­ی یک صفحه را بدون داشتن مقدار نهایی امتیاز صفحه­ی صفحات دیگر محاسبه کنیم. اما این به نظر عجیب است. اما در واقع هر بار که محاسبات را تکرار کنیم تخمینی نزدیک­تر به مقدار نهایی را به دست می­آوریم.

 

بنابراین باید هر مقداری که محاسبه کردیم را نگه داریم و محاسبات را چند بار تکرار کنیم تا زمانیکه اعداد زیاد تغییر نکنند. بیایید ساده ترین مثال را در نظر بگیریم. 2 صفحه داریم که هر کدام به دیگری اشاره می­کنند ، هر صفحه یک پیوند خروجی دارد و C(A)=1 ، C(B)=1 می­باشد. ما نمی­دانیم برای شروع امتیاز صفحه آنها چیست.

 

حدس 1 : پس بیایید یک حدس بزنیم و محاسبات را با مقدار 1 شروع کنیم :

 

 

 

 

 

 

 

شکل (1-1)  یک سلسله مراتب ساده از ارتباط بین دو صفحه

 

d = 0.85

 

PR(A) = (1-d) + d(PR(B)/1)

 

PR(B) = (1-d) + d(PR(A)/1)

 

مثل :

 

PR(A) = 0.15 + 0.85 * 1 = 1

 

PR(B) = 0.1 5+ 0.85 * 1 = 1

 

می­بینید که اعداد تغییر نکرده اند. به نظر می­آید با یک عدد خوب شروع نکرده ایم.

 

حدس 2 : بیایید اکنون با صفر شروع کرده و محاسبات را 2 باره انجام دهیم.

 

PR(A) = 0.15 + 0.85 * 0 =0.15

 

حالا از مقدار PR(A) که حساب کرده ایم در همین جا استفاده می­کنیم.

 

PR(B) = 0.15 + 0.85 * 0.15 = 0.2775

 

و دوباره :

 

PR(A) = 0.15 + 0.85 * 0.2775 = 0.385875

 

PR(B) = 0.15 + 0.85 * 0.385875 = 0.47799375

 

و دوباره :

 

PR(A) = 0.15 + 0.85 * 0.47799375 = 0.5562946875

 

PR(B) = 0.15 + 0.85 * 0. 5562946875 = 0.622850484375

 

 

 

و به همین صورت اعداد به بیشتر شدن ادامه می­دهند.

 

اما آیا افزایش اعداد بعد از رسیدن به 1 متوقف می­شود ؟ چه می­شود اگر به وقدار بیشتر از 1 برسیم ؟

 

حدس 3 : بیایید با مقدار 40 شروع کرده و محاسباتی را انجام دهیم.

 

PR(A) = 40 , PR(B) = 40

 

اولین محاسبه :

 

PR(A) = 0.15 + 0.85 * 40 =34.15

 

PR(B) = 0.15 + 0.85 * 34.15 = 29.1775

 

و دوباره :

 

PR(A) = 0.15 + 0.85 * 29.1775 = 24.950875

 

PR(B) = 0.15 + 0.85 * 24.950875 = 21.35824375

 

می­بینید که اعداد با هر محاسبه دارند کاهش می­یابند. این اطمینان می­دهد که اعداد به 1 خواهند رسید و متوقف می­شوند.

 

اصل : مهم نیست حدس خود را از کجا شروع کنید ، هنگامی که محاسبات امتیاز صفحه پایان گرفت ، به توزیع احتمال نرمال برابر 1 خواهید رسید ]8[.

 

1-1-4- گرفتن پاسخ با سرعت بیشتر

 

برای شبکه­های بزرگ چند بار محاسبات را تکرار کنیم ؟ این یک سوال مشکل است. برای شبکه ای به بزرگی وب جهانی ممکن است نیاز باشد چند میلیون بار محاسبات را تکرار کنیم. فاکتور تعدیل تا حدی هوشمند عمل می­کند. اگر خیلی بالا باشد ، مدت­ها طول می­کشد تا اعداد ثابت شوند و اگر خیلی پایین باشد ، تعداد تکرار بسیار زیاد می­شود.

 

هم چنین انتخاب ترتیب محاسبات می­تواند کمک کند. نتیجه در هر صورت یکسان است و ترتیبی که انتخاب می­شود مهم نیست. اما بعضی ترتیب­ها زودتر از بقیه شما را به نتیجه می­رساند. در مثال­های زیر کدهای ساده ای برای روشن کردن استفاده شده و تقریباً 20 تا 40 تکرار برای آن نیاز است ]3[.

 

مثالی از محاسبه­ی امتیاز صفحه

 

در این بخش الگوریتم امتیاز صفحه را روی چند ساختار متفاوت از ارتباط میان صفحات اعمال می­کنیم تا بر با بررسی نتایج حاصل بتوانبم نتیجه بگیریم که آیا ساختار سلسله مراتب و پیونددهی صفحات وب روی امتیازدهی تاثیر دارد و هم چنین چه ساختارهایی باعث افزایش امتیاز صفحه و چه ساختارهایی موجب کاهش آن می­شوند.

 

- مثال 1

 

برای رسیدن به این مقادیر 20 بار محاسبات را تکرار کرده ایم. به صفحه­ی D توجه کنید. با اینکه کسی به آن رای نداد است ، امتیاز صفحه­ی آن 0.15 می­باشد.

 

بنابراین برای صفحه D که هیچ پیوند ورودی ندارد معادله به این شکل در می­آید :

 

PR(A) = (1-d) + d * (0) = 0.15

 

نکته : هر صفحه حداقل امتیاز صفحه­ی 0.15 را دارد که آن را بین صفحاتی که به آن­ها پیوند می­دهد ، به اشتراک می­گذارد. اما این ممکن است تنها یک تئوری باشد. اما شایعاتی در مورد گوگل وجود دارد که در آن هر صفحه ای که هیچ پیوند ورودی ندارد ، هرگز کاملا از اندیس پاک نمی­شود ( پیوندهای معلق ).